package com.lzy.algorithm;

import java.util.Arrays;

/**
 * Author: lzy
 * Date:   2020/06/19 14:43
 * Description:
 **/
public class 快速排序 {

    public static void main(String[] args) {
        int[] nums = new int[]{8, 4, 6, 1, -1, 5, 0};
        fastSortArray(nums, 0, nums.length - 1);
        System.out.println(Arrays.toString(nums));
    }

    public static void fastSortArray(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int partition = getPartition(nums, left, right);
        fastSortArray(nums, left, partition - 1);
        fastSortArray(nums, partition + 1, right);
    }

    public static int getPartition(int[] nums, int left, int right) {
        int startIndex = left;
        int partition = nums[left];
        while (left < right) {
            while (left < right && nums[right] >= partition) {
                right--;
            }
            while (left < right && nums[left] <= partition) {
                left++;
            }

            if(left < right){
                int tmp = nums[left];
                nums[left] = nums[right];
                nums[right] = tmp;
            }
        }

        int tmp = nums[startIndex];
        nums[startIndex] = nums[left];
        nums[left] = tmp;

        return left;
    }
}
